#include <stdio.h>
#include <stdlib.h>

#define SIZE 20

void random(int *a);
void output(int *a);
void insertSort(int *a);
int search(int a[],int n,int k);//顺序查找 
int binSearch1(int a[],int n,int k);//二分查找的非递归算法 
int binSearch2(int a[],int low,int high,int k);//二分查找的递归算法

int main(int argc, char *argv[])
{
    int a[SIZE],t;
    random(a);//调用随机生成数的函数 
    printf("随机生成的%d个数：",SIZE);
    output(a);//调用输出函数 
    printf("请输入要查找的数(0到%d之间)：",SIZE);
    scanf("%d",&t);
    printf("顺序查找%d的结果，下标为：%d\n",t,search(a,SIZE,t));//顺序查找 
    insertSort(a);//插入排序         
    printf("排序后的%d个数：",SIZE); 
    output(a);//调用输出函数 
    //printf("二分查找%d的结果，下标为%d\n",t,binSearch1(a,SIZE,t));//二分查找非递归算法 
    printf("二分查找%d的结果，下标为%d\n",t,binSearch2(a,0,SIZE,t));//二分查找递归算法
  
  system("PAUSE");	
  return 0;
}


/*
随机生成SIZE个整数
*/
void random(int *a)
{
     int i;
     srand((unsigned)time(NULL));//设置随机数的种子
	for(i=0;i<SIZE;i++)
	{
		a[i]=rand()%SIZE;
	}
}
//输出数组中的元素
void output(int *a)
{
     int i;
    for(i=0;i<SIZE;i++)
	{
		printf("%3d",a[i]);;		
	}
	printf("\n");	
}

/* 直接插入排序，基本思想是：顺序的把待排序的数据元素按其值的大小
插入到已排序的数据元素子集合的适当位置。
子集合的数据元素个数从只有一个数据元素开始逐次增大。
当子集合大小最终和集合大小相同时排序完毕
*/
void insertSort(int *a)
{
    int i,j,temp;//i，j为循环的下标，temp临时保存值
			
	for(i=0;i<SIZE-1;i++){
		temp=a[i+1];//先把下标为i+1的元素的值保存
		j=i;
		while(j>-1&&temp<a[j]){//在下标为i之前的元素中找到temp应该插入的位置
			a[j+1]=a[j];
			j--;
		}
		a[j+1]=temp;//把temp插入到前面有序的数据元素中
	}
}

//顺序查找 
int search(int a[],int n,int k)
{
	int i=0;
	while(i<n)
		if(a[i]!=k)
			i++;
		else 
			return i;
	return -1;
}

//二分查找的非递归算法 
int binSearch1(int a[],int n,int k)
{
    int low,high,mid;
    low=0;
    high=n-1;
    while(low<=high)
    {
        mid=(low+high)/2;
        if(k==a[mid])
            return mid;
        else if(k<a[mid])
            high=mid-1;
        else 
            low=mid+1;
    }
    return -1;
}

//二分查找的递归算法 
int binSearch2(int a[],int low,int high,int k)
{
    int mid;
    if(low>high)
        return -1;
    else{
        mid=(low+high)/2;
        if(k==a[mid])
            return mid;
        else if(k<a[mid])
            return binSearch2(a,low,mid-1,k);
        else 
            return binSearch2(a,mid+1,high,k);
    }
}
